package com.zlk.algorithm.algorithm.tools.slidingWindow049;

import org.junit.Test;

import java.util.*;

// 最小覆盖子串
// 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串
// 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
// 测试链接 : https://leetcode.cn/problems/minimum-window-substring/
public class Code03_MinimumWindowSubstring {

    @Test
    public void test(){
        //System.out.println(minWindow("a", "a"));
        System.out.println(minWindow2("cabwefgewcwaefgcf", "cae"));
    }

    //滑动窗口
    //实现逻辑
    //把t换成一个欠债表，如何转换见图示，记录一个总的欠债数目
    // 维护滑动窗口，r每次去吸纳数据，如果数据不是欠债表中的数据，直接加入进去，但是总欠债数目不累加，因为不是目标还款，理解送的
    //  如果是欠债表中的目标数据，则将目标对象的数据减1 ，并且总数目减1，
    // 当总数目为0时。说明已经还完了，此时L移动，判断L能向右移动，
    // 1、如果l数据不是目标对象而是之前r送的数据，此时可以移除l++,
    // 2、如果l数据是目标对象
    //   a:如果目标对象是大于0d的此时可以移除 并且 l++
    //   b:如果是等于0 统计此区间的ans 信息， 然后 l++ ，l++的含义相当于把l的数据又欠了回去，所以要去维护一下欠债表，以及总欠债数，然后r++

    //总而言之就是 r走到 欠债表为0才会停，l走到是目标对象才会停
    public String minWindow2(String s, String t) {
        char[] chars = s.toCharArray();
        char[] debtArr = t.toCharArray();
        HashMap<Character,Integer> debtMap = new HashMap<>();
        //总欠债数目
        int debtCount = t.length();
        for (int i = 0; i < debtArr.length; i++) {
            char key = debtArr[i];
            if(debtMap.containsKey(key)){
                debtMap.put(key,debtMap.get(key)+1);
            }else{
                debtMap.put(key,1);
            }
        }
        //非目标字符
        HashMap<Character,Integer> otherMap = new HashMap();
        int start = 0;
        int len = Integer.MAX_VALUE;
        for (int l = 0,r=0; r < chars.length; r++) {
            //区间不满足
            char val =  chars[r];
            //是否是目标字符
            if(debtMap.containsKey(val)){
                if(debtMap.get(val)>0){
                    debtCount--;
                }
                debtMap.put(val,debtMap.get(val)-1);
            }else{
                //不是目标串
                if(otherMap.containsKey(val)){
                    otherMap.put(val,otherMap.get(val)+1);
                }else{
                    //第一次进入
                    otherMap.put(val,1);
                }
            }
            if(debtCount==0){
                // 欠债换完，区间满足
                // l移动
                char val2 = chars[l];

                //收缩区间
                while (otherMap.containsKey(val2)||debtMap.get(val2)<0){
                    l++;
                    if(otherMap.containsKey(val2)){
                        //能缩
                        Integer old = otherMap.get(val2);
                        if(old==1){
                            otherMap.remove(val2);
                        }else{
                            otherMap.put(val2,old-1);
                        }
                    }else{
                        //只能是目标字符
                        Integer old = debtMap.get(val2);
                        debtMap.put(val2,old+1);
                    }
                    val2 = chars[l];
                }
                //找到满足的区间
                len = Math.min(len,r-l+1);
                start = l;
                Integer old = debtMap.get(val2);
                debtMap.put(val2,old+1);
                debtCount++;
                l++;

            }
        }
        return  len==Integer.MAX_VALUE?"":s.substring(start,start+len);
    }


    /**
     * 递归解法
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        if(s.length()<t.length()){
            return "";
        }
        char[] chars = s.toCharArray();
        char[] debt = t.toCharArray();
        HashMap<Character,Integer> DebtMap = new HashMap<>();

        for (int i = 0; i < debt.length; i++) {
            char key = debt[i];
            if(DebtMap.containsKey(key)){
                DebtMap.put(key,DebtMap.get(key)+1);
            }else{
                DebtMap.put(key,1);
            }
        }
        int len = Integer.MAX_VALUE;
        int start =0;
        for (int i = 0; i < chars.length; i++) {
            HashMap tempMap = new HashMap();
            tempMap.putAll(DebtMap);
            int flen = f(i,chars,tempMap);
            if(flen>0&&flen<len){
                len = flen;
                start = i;
            }
        }
        return len==Integer.MAX_VALUE?"":s.substring(start,start+len);
    }

    private int f(int i,char[] chars, HashMap<Character,Integer> debtMap) {
        if(chars.length==i&&debtMap.size()>0){
            return Integer.MIN_VALUE;
        }else if(debtMap.size()==0){
            return 0;
        }else{
            char key = chars[i];
            if(debtMap.containsKey(key)){
                Integer val = debtMap.get(key);
                if(val==1){
                    debtMap.remove(key);
                }else{
                    debtMap.put(key,val-1);
                }
            }
            return f(i+1,chars,debtMap)+1;
        }
    }

}
